A semiconductor integrated circuit (IC) has a large number of electronic components, such as transistors, logic gates, diodes, wires, etc., that are fabricated by forming layers of different materials and of different geometric shapes on various regions of a silicon wafer. The design of an integrated circuit transforms a circuit description into a geometric description called a layout. The process of converting specifications of an integrated circuit into a layout is called the physical design. After the layout is complete, it is then checked to ensure that it meets the design requirements. The result is a set of design files, which are then converted into pattern generator files. The pattern generator files are used to produce patterns called masks by an optical or electron beam pattern generator. Subsequently, during fabrication of the IC, these masks are used to pattern chips on the silicon wafer using a sequence of photolithographic steps. Electronic components of the IC are therefore formed on the wafer in accordance with the patterns.
Many phases of physical design may be performed with computer aided design (CAD) tools or electronic design automation (EDA) systems. To design an integrated circuit, a designer first creates high level behavior descriptions of the IC device using a high-level hardware design language. An EDA system typically receives the high level behavior descriptions of the IC device and translates this high-level design language into netlists of various levels of abstraction using a computer synthesis process. A netlist describes interconnections of nodes and components on the chip and includes information of circuit primitives such as transistors and diodes, their sizes and interconnections, for example.
Geometric information about the placement of the nodes and components onto the chip is determined by a placement process and a routing process. The placement process is a process for placing electronic components or circuit blocks on the chip and the routing process is the process for creating interconnections between the blocks and components according to the specified netlist.
IC layouts are often constructed in a hierarchical fashion, in which a master version or occurrence of a particular geometric element is created once, but where one or more instances of the geometric element may be inserted into various locations and levels within the IC design. In this type of approach, the IC layout is hierarchically set out by re-using elements over and over again. Rather than copying duplicates of the same geometric element everywhere that it is used, instances of the elements are inserted in the appropriate locations that logically reference the appropriate master occurrence or version.
FIG. 1A shows an example design hierarchy, in which an occurrence 112 of element A comprises three shapes 114, 116, and 118. As used herein, occurrence is a master or reference copy of an element and an instance is an instantiation of an occurrence. At a different level in the IC design, an occurrence 122 of element B may be created that includes its own shapes 124 and 125, as well as two instances 126 and 128 of element A. At yet another level of the IC design, an occurrence 132 for element C may be created that includes a shape 134 as well as two instances 136 and 138 of element B. Instances 136 and 138 each contain instances of element A as shown in occurrence 122 (which are “nested instances”). In the hierarchy of FIG. 1A, each instance provides a logical reference to its master occurrence rather than a physical manifestation of the occurrence at the instance locations. Assume that shapes 114, 116, and 134 are on layer 1 of the design and shapes 118, 124, and 125 are on layer 2 of the design. FIG. 1B shows the shapes that would be present on layer 1 for these portions of the design and FIG. 1C shows the shapes that would be present on layer 2.
An advantage of this approach is improved efficiency with respect to memory usage when storing design data for an IC design. Memory efficiencies are gained since instances of an element are used and placed in the design, rather than requiring a full copy of that element to be duplicated numerous times in the design data.
However, the hierarchical nature of this approach can also cause inefficiencies when attempting to access the design data. As just one example, consider the process to search a portion of the IC design for the shapes within a particular search area. The search area may encompass parts of one or more instances in the design. However, only a subset of the shapes within the instances may actually fall within the search area. Because the shapes are not actually stored at each level, the search process may need to traverse the entire hierarchy of the corresponding instances on every layer and their nested instances to confirm which shapes in the instances relate to the search area, even through portions of the hierarchy that do not contain any shapes at the correct layer or design area. Depending upon the complexity of the design, this could be a very lengthy and expensive process.
In an alternate approach, the design hierarchy can be flattened so that the design data is not hierarchical in nature. In this approach, rather than inserting instances of elements into the design, actual copies of the elements are placed in the appropriate locations within the design data. FIG. 2 shows a flattened version of the design data shown in FIG. 1. Here, occurrence 122a for a flattened element B includes copies 126a and 128a of element A 112, rather than the instances 126 and 128 of element A shown in FIG. 1 that refers back to the master copy 112. Similarly, occurrence 132a for a flattened element C includes copies 136a and 138a of element B 122a, rather than instances that refer back to the master copy. The advantage of this approach is that it is very efficient to search the flattened design data, since chains of instances do not need to be followed to identify shapes within a search area. However, if the design includes a large number of geometric elements, then this approach may also consume an excessive amount of memory and storage resources.
A useful function for EDA software is to identify all shapes that may be connected to an initially identified shape. The connected shapes may be on the same hierarchical level layer of a design or on different hierarchical levels. The connected shapes may be on the same layer of a design or on different layers connected through vias.
In traditional EDA systems, these operations for identifying and tracking connected shapes require the IC design to be a flat design. In part, this is because traditional approaches need the design to be flat to allow efficient identification of shapes that geometrically overlap with each other. If the design is originally in a hierarchical format, then the design must be flattened/unfolded before performing the operations to extract or verify the sets of connected shapes. One possible drawback of this traditional approach is that if the design includes a large number of geometric elements, then working with an unfolded design may also consume an excessive amount of memory and storage resources to store numerous copies of the exact same design elements/shapes, which could negatively affect the performance and usability of the system. Moreover, if the design is originally in a hierarchical format, then the process of flattening the entire design could itself be excessively expensive and delay the overall results.
Therefore, it is desirable to implement an improved method and mechanism for identifying and verifying connected shapes in the hierarchical design for an integrated circuit that address these drawbacks of the traditional approaches. In particular, it is desirable to have a method and mechanism for identifying connected shapes in a hierarchical design which do not require the entire hierarchical design to be fully flattened.